package leetcode_core.leetcode_1;

import org.junit.Test;

public class MinDistanceByDPTable {
    public int minDistance(String word1, String word2) {
        //1.定义dp数组
        int[][] dp = new int[word1.length()+5][word2.length()+5];
        //2.写出base-case
        //当j走完的时候其下标是-1,但是java中下标是没有-1,因此我们将指针加上一个偏移量(+1)
        //for(int i = 0;i<word1.length();i++){
            //dp[i][0] = i-1;
        //}
        //变成:
        for(int i = 1;i<=word1.length();i++){//当j已经走到了-1的据欧
            dp[i][0] = i;
        }
        for(int j = 1;j<=word2.length();j++){
            dp[0][j] = j;
        }
        //3.穷举所有选择,根据状态转移方程编码
        //等号以及开始下标怎么确定呢?
        //我们来看:首先开始下标是要根据base-case来确定的,推算的起点应该比base-case多一个级别
        //比如说base-case确定的是下标为0的所有数字,那么我开始推算就应该从0+1(不知道的地方)开始推算
        //等号的话就是我最终答案包含在哪个范围之内,我要用哪些数据
        //我最终的答案都是要用word.length()-1这个数据的来推算的,所以我应该在计算时把=包含进去
        for(int i=1;i<=word1.length();i++){
            for(int j=1;j<=word2.length();j++){
                if(word1.charAt(i-1) == word2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }else {
                    dp[i][j] = Math.min(Math.min(dp[i-1][j-1]+1,dp[i-1][j]+1),dp[i][j-1]+1);
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }

    @Test
    public void test(){
        System.out.println(minDistance("horse","ros"));
    }
}
